Papers with quadratic computational cost
State-offset Tuning: State-based Parameter-Efficient Fine-Tuning for State Space Models (2025.acl-short)
Copied to clipboard
| Challenge: | State Space Models (SSMs) have emerged as efficient alternatives to Transformers, but their application to SSMs remains unexplored. |
| Approach: | They propose a state-based PEFT method that adjusts state directly instead of using external prompts. |
| Outcome: | The proposed method is based on state-offset tuning, which directly affects state at every timestep. |
Fine- and Coarse-Granularity Hybrid Self-Attention for Efficient BERT (2022.acl-long)
Copied to clipboard
| Challenge: | Transformer-based pre-trained models achieve state-of-the-art results, but they can be prohibitively costly. |
| Approach: | They propose a fine- and coarse-granularity hybrid self-attention that shortens the computational sequence length in self- attention by progressively shortening the computational time. |
| Outcome: | The proposed model reduces computation cost by shortening the computational sequence length in self-attention. |
Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers (2025.findings-emnlp)
Copied to clipboard
| Challenge: | a large computational cost for attention computation in large language models is a major obstacle . |
| Approach: | They propose a convolution-like structure for attention computation using convolution matrices . they then propose an efficient approximation method to approximate the attention matrix . |
| Outcome: | The proposed method achieves nearly linear time complexity in n1+o(1) time. |
MATCH: Modulating Attention via In-Context Retrieval for Long-Context Transformers (2026.acl-long)
Copied to clipboard
Linrui Ma, Chun Hei Lo, Xinyu Wang, Peng Lu, Xihao Yuan, Hanting Chen, Kai Han, Xinghao Chen, Chengjun Zhan, Hanlin xu, Yichun Yin, Lifeng Shang, Feng Wen, Boxing Chen, Yufei Cui
| Challenge: | Existing approaches to improve efficiency often enforce rigid structural constraints such as local attention windows. |
| Approach: | They propose a framework that augments sparse-attention mechanisms with dynamically integrated in-context information through an efficient retrieval system. |
| Outcome: | Empirical results show that MATCH significantly improves the performance of sparse-attention models on synthetic and real-world natural-language tasks. |